#include <stdio.h>
#include <string.h>
#include <netdb.h>
#include <stdlib.h>
#include <errno.h>
#include <unistd.h>
#include <poll.h>
#include <ifaddrs.h>
#include <netinet/in.h>
#include <netinet/ip.h>
#include <linux/types.h>
#include <linux/icmp.h>

//yes I can find it in headers, but I want to do it myself
#pragma pack(push ,1)
struct ip_header_t {
  unsigned version : 4;
  unsigned header_len : 4;
  __u8     tos;
  __u16    total_len;
  __u16    id;
  unsigned flags : 3;
  unsigned frag_offset : 13;
  __u8     ttl;
  __u8     proto;
  __u16    checksum;
  __u32    source;
  __u32    dest;
};

struct icmp_echo_t {
  __u8 type;
  __u8 code;
  __u16 checksum;
  __u16 id;
  __u16 snum;
  __u8 data[56];
};

struct icmp_header_t {
  __u8 type;
  __u8 code;
  __u16 checksum;
  __u16 content[2];
};

struct icmp_time_exceed_data_t {
  struct ip_header_t ip_header;
  struct icmp_echo_t echo;
};

struct net_response_t {
  struct ip_header_t ip_header;
  struct icmp_header_t icmp_header;
  struct icmp_time_exceed_data_t time_exceed;
};

#pragma pack(pop)
struct ifaddrs *if_head;

__u16 ip_checksum(__u16 *data, int len) {
  __u32 sum = 0;

  while (len > 1)  {
    sum += *data++;
    len -= 2;
  }
  
  sum = (sum >> 16) + (sum & 0xffff);
  sum += (sum >> 16);
  return (__u16)~sum;
}

int main(int argc, char** argv) {
  int ret = 0;
  if (argc < 2) {
    printf("args: [ip address]\n");
    printf("example: trace_route 192.168.1.1\n");
    return -1;
  }
  errno = 0;
  in_addr_t target_ip = inet_addr(argv[1]);
  if (errno || !target_ip) {
    printf("ERROR: invalid ip\n");
    return -1;
  }
  char* if_name = argv[2];
  errno = 0;

  struct sockaddr_in sender_addrs_in;
  sender_addrs_in.sin_family = AF_INET;
  sender_addrs_in.sin_port = 0;
  sender_addrs_in.sin_addr.s_addr = INADDR_ANY;
  
  errno = 0;
  int sock_sender = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
  int sock_recv = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
  __u32 icmp_type_filter = ~(1 << ICMP_TIME_EXCEEDED | 1 << ICMP_ECHOREPLY);
  setsockopt(sock_recv, SOL_RAW, ICMP_FILTER, (char*)&icmp_type_filter, sizeof(icmp_type_filter));
  if (errno) {
    perror("Error opening socket: ");
    return -1;
  }

  errno = 0;
  ret = bind(sock_sender, (struct sockaddr*)&sender_addrs_in, sizeof(struct sockaddr_in));
  ret = bind(sock_recv, (struct sockaddr*)&sender_addrs_in, sizeof(struct sockaddr_in));
  if(ret) {
    perror("Error binding socket: ");
    return -1;
  }
  errno = 0;

  struct sockaddr_in target_addr_in;
  target_addr_in.sin_family = AF_INET;
  target_addr_in.sin_port = 0;
  target_addr_in.sin_addr.s_addr = target_ip;

  struct icmp_echo_t echo;
  echo.type = 8;
  echo.code = 0;
  echo.id = getpid();
  echo.snum = 0;
  echo.checksum = 0;
  echo.checksum = ip_checksum((__u16*)&echo, sizeof(struct icmp_echo_t));

  size_t ttl;
  struct net_response_t resp;
  struct sockaddr_in node_addr_in;
  socklen_t sockaddr_in_size = 0;
  size_t node_counter = 0;
  for(ttl = 1; 1; ++ttl) {
    size_t ttl_tries = 0;
    for (; ttl_tries < 5; ++ttl_tries) {
      setsockopt(sock_sender, SOL_IP, IP_TTL, &ttl, sizeof(ttl));
      echo.snum = htons(ntohs(echo.snum) + 1);
      echo.checksum = 0;
      echo.checksum = ip_checksum((__u16*)&echo, sizeof(struct icmp_echo_t));
      sendto(sock_sender, &echo, sizeof(struct icmp_echo_t), 0, (struct sockaddr*)&target_addr_in, sizeof(struct sockaddr_in));
      struct pollfd pfd;
      int ret;  
      pfd.fd = sock_recv;
      pfd.events = POLLIN;  
      ret = poll(&pfd, 1, 1000);
      if (ret <= 0) {
        continue;
      }

      size_t read =recvfrom(sock_recv, &resp, sizeof(struct net_response_t), 0,
                          (struct sockaddr*)&node_addr_in, &sockaddr_in_size);

      if (resp.icmp_header.type == 11 ) {
        if (resp.time_exceed.echo.id == getpid()) {
          __u8 *ip = (char*)&node_addr_in.sin_addr.s_addr;
          if (ip[0] == ip[1] && ip [2] == ip[3] && ip[1] == ip[2] && !ip[0]) {
            continue;
          }
          printf("%d: %d.%d.%d.%d\n", node_counter, ip[0], ip[1], ip[2], ip[3]);
          //__u8 *ip1 = (char*)&resp.time_exceed.ip_header.source;
          //printf("%d.%d.%d.%d\n", ip1[0], ip1[1], ip1[2], ip1[3]);
          //__u8 *ip2 = (char*)&resp.time_exceed.ip_header.dest;
          //printf("%d.%d.%d.%d\n\n", ip2[0], ip2[1], ip2[2], ip2[3]);
          ++node_counter;
          break;
        }
      } else {
        //printf("type: %d code: %d id: %d\n", resp.icmp_header.type, resp.icmp_header.code, ntohs(resp.icmp_header.content[0]));
        if (resp.icmp_header.type == 0 && resp.icmp_header.code == 0) {
          struct icmp_echo_t *as_echo = (struct icmp_echo_t*)&resp.icmp_header;
          if (as_echo->id == getpid()) {
            __u8 *ip = (char*)&target_ip;
            printf("%d: %d.%d.%d.%d\n", node_counter, ip[0], ip[1], ip[2], ip[3]);
            goto end;
          }
        }
      }
    }
  }
  end:
  close(sock_recv);
  close(sock_sender);
  freeifaddrs(if_head);
  return 0;
}
